#include "Heap.h"

void HeapInit(Heap* php) {
	assert(php);
	php->_a = NULL;
	php->_capacity = php->_size = 0;
}

void HeapDestroy(Heap* php) {
	if (php == NULL) {
		return;
	}
	free(php->_a);
	php->_a = NULL;
	php->_capacity = php->_size = 0;
	free(php);
	php = NULL;
}

Heap* HeapCreate() {
	Heap* php = (Heap*)malloc(sizeof(Heap));
	if (php == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	HeapInit(php);
	return php;
}

void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void Extend(Heap* php) {
	assert(php);
	php->_capacity = php->_capacity == 0 ? 4 : 2 * php->_capacity;
	HPDataType* tmp = (HPDataType*)realloc(php->_a, php->_capacity * sizeof(HPDataType));
	if (tmp == NULL) {
		perror("realloc fail!");
		exit(2);
	}
	php->_a = tmp;
}

void HeapAdjustUp(HPDataType* arr, int child, const char type) {
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (arr[child] < arr[parent] && type == 'S') {
			Swap(&arr[child], &arr[parent]);
			HeapAdjustUp(arr, parent, type);
		}
		else if (arr[child] > arr[parent] && type == 'B') {
			Swap(&arr[child], &arr[parent]);
			HeapAdjustUp(arr, parent, type);
		}
		else {
			child--;
		}
	}
}

void HeapAdjustDown(HPDataType* arr, const int size, int parent, const char type) {
	int child = 2 * parent + 1;
	while (child < size) {
		if (child > 2 * parent + 2) {
			break;
		}
		if (arr[parent] > arr[child] && type == 'S') {
			Swap(&arr[parent], &arr[child]);
			HeapAdjustDown(arr, size, child, type);
		}
		else if (arr[parent] < arr[child] && type == 'B') {
			Swap(&arr[parent], &arr[child]);
			HeapAdjustDown(arr, size, child, type);
		}
		else {
			child++;
		}
	}
}

void HeapPush(Heap* php, const HPDataType num, const char type){
	if (type != 'S' && type != 'B') {
		printf("wrong type!\n");
		return;
	}
	assert(php);
	if (php->_capacity <= php->_size) {
		Extend(php);
	}
	php->_a[php->_size++] = num;
	HeapAdjustUp(php->_a, php->_size - 1, type);
}

void HeapPop(Heap* php, const char type) {
	if (type != 'S' && type != 'B') {
		printf("wrong type!\n");
		return;
	}
	assert(php);
	php->_a[0] = php->_a[php->_size - 1];
	php->_size--;
	HeapAdjustDown(php->_a, php->_size, 0, type);
}

HPDataType HeapTop(Heap* php) {
	assert(php);
	if (php->_size > 0) {
		return php->_a[0];
	}
	else {
		printf("Heap is NULL!\n");
		return -1;
	}
}

int HeapSize(Heap* php) {
	assert(php);
	return php->_size;
}

bool HeapEmpty(Heap* php) {
	assert(php);
	if (php->_size > 0) {
		return false;
	}
	else {
		return true;
	}
}

//void HeapSort(int* arr, int size) {
//	int child = size - 1;
//	int parent = (child - 1) / 2;
//	while (child > 0) {
//		if (arr[child] < arr[parent]) {
//			Swap(&arr[child], &arr[parent]);
//			HeapSort(arr, parent);
//		}
//		else {
//			child--;
//		}
//	}
//}